import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 2558. 从数量最多的堆取走礼物
 */
public class No2558 {
    public long pickGifts(int[] gifts, int k) {
        Queue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int gift : gifts) {
            heap.offer(gift);
        }
        for (int i = 0; i < k; i++) {
            int pow = (int) Math.pow(heap.poll(), (double) 1 / 2);
            System.out.println(pow);
            heap.offer(pow);
        }
        long ans = 0;
        for (Integer i : heap) {
            ans += i;
        }
        return ans;
    }
}
